from collections import deque
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy_node = ListNode(-1, head)
        prev = None
        curr = head
        if not curr: return None
        next = curr.next
        while next is not None:
            curr.next = prev
            prev = curr
            curr = next
            next = next.next
        curr.next = prev
        return curr


if __name__ == '__main__':
    s = Solution()
    nodes = deque()
    v = [1, 2, 3, 4, 5]
    for i in range(len(v) - 1, -1, -1):
        if i < len(v) - 1:
            node = ListNode(v[i], nodes[0])
        else:
            node = ListNode(v[i], None)
        nodes.appendleft(node)
    r = s.reverseList(nodes[0])
    while r:
        print(r.val, end=' ')
        r = r.next
